/**
 * 有效的括号:
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 * 有效字符串需满足：
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 每个右括号都有一个对应的相同类型的左括号。
 */

// 输入: '()'        --->    输入: true
// 输入: '()[]{}'    --->    输入: true
// 输入: '(])'       --->    输入: false
// 输入: '{()}'      --->    输入: true

/**
 * 解题步骤
 * 1. 新建一个栈(新建一个数组)
 * 2. 扫描字符串, 遇到左括号入栈, 遇到和栈顶(数组的最后一位) 类型匹配的右括号就出栈, 类型不匹配直接判定不合法
 * 3. 最后栈空了就合法, 否则就不合法
 */

// 时间复杂度: O(n)
// 空间复杂度: O(n)

// 输入: '()'        --->    输入: true
// 输入: '()[]{}'    --->    输入: true
// 输入: '(])'       --->    输入: false
// 输入: '{()}'      --->    输入: true

const isValid = (s) => {
  if (s % 2 === 1) return false
  // 新建一个栈
  const stack = []
  for (let i = 0; i < s.length; i++) {
    const c = s[i]
    if (c === '(' || c === '{' || c === '[') {
      // 入栈
      stack.push(c)
    } else {
      // 判断栈顶(数组的最后一位)是否匹配
      const t = stack[stack.length - 1]
      if (
        (t === '(' && c === ')') ||
        (t === '{' && c === '}') ||
        (t === '[' && c === ']')
      ) {
        // 出栈
        stack.pop()
      } else {
        return false
      }
    }
  }

  return stack.length === 0
}

console.log(isValid('()'))
console.log(isValid('()[]{}'))
console.log(isValid('(])'))
console.log(isValid('{()}'))
